/*
题目: 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
 */
public class Offer51 {
    int res = 0;

    //归并排序
    public int reversePairs(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return res;
    }

    private void mergeSort(int[] nums, int start, int end) {
        //先分再合并
        if (start >= end) { //只剩一个元素就不分了
            return ;
        }
        int mid = start + ((end - start) >> 1);
        mergeSort(nums, start, mid);
        mergeSort(nums, mid + 1, end);

        merge(nums, start, mid, end);
    }

    private void merge(int[] nums, int start, int mid, int end) {
        int start1 = start;
        int start2 = mid + 1;
        int[] tmpArr = new int[end - start + 1];
        int k = 0;

        //开始并
        while (start1 <= mid && start2 <= end) {
            if (nums[start1] <= nums[start2]) {
                tmpArr[k++] = nums[start1++];
            } else {
                res += mid - start1 + 1;
                tmpArr[k++] = nums[start2++];
            }
        }
        while (start1 <= mid) {
            tmpArr[k++] = nums[start1++];
        }
        while (start2 <= end) {
            tmpArr[k++] = nums[start2++];
        }
        //并完成

        for (int i = 0; i < k; i++) {
            nums[i + start] = tmpArr[i];
        }
    }
}
